package edu.kmust.simple;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @author : 常伟
 * @date: 2019/3/8 16:14
 * @email: kmustchang@qq.com
 * @Description: 第七题：夜过吊桥的第一种方法，采用的是回溯法
 */
public class ExaminationSeven01 {

    /**这个表示玩家的状态，0表示还没有过桥，1表示已经过桥*/
    int[] state=new int[4];
    /**这个表示各个玩家过桥需要的时间，这个时间必须是从小到大的顺序*/
    int[] time=new int[4];
    /**这个表示最终需要的时间*/
    int result=Integer.MAX_VALUE;
    /**这个表示某一个过桥需要的总时间，有可能不是最短的，他只表示某一次完成过桥需要的时间*/
    int resultTemp=0;
    /**这个表示某一次过桥的路径，有可能不是最短的路径，只是表示某一次完成过桥的路径*/
    ArrayList<String> resultPathTemp =new ArrayList<>(10);
    /**这个表示最终最短的过桥路径*/
    ArrayList<String> resultPath;

    public static void main(String[] args) {
        ExaminationSeven01 examinationSeven01=new ExaminationSeven01();
        examinationSeven01.init();
        examinationSeven01.computeTime();
        System.out.println(examinationSeven01.result);
        System.out.println(examinationSeven01.resultPath);
    }

    /**
     * 功能：完成过桥的需要的时间
     */
    private void computeTime() {
        if(complete()){
            if(resultTemp<result){
                resultPath =new ArrayList<>(resultPathTemp);
                result=resultTemp;
            }
            return;
        }
        int returnTime=returnTime();
        resultTemp+=returnTime;
        for(int i=0;i<3;i++){
            for(int j=i+1;j<4;j++){
                if(i!=j && state[i]==state[j]&&state[i]==0){
                    state[i]=1;
                    state[j]=1;
                    resultPathTemp.add((i+1)+" "+(j+1));
                    int maxTime=time[i]>time[j]?time[i]:time[j];
                    resultTemp+=maxTime;
                    computeTime();
                    resultPathTemp.remove(resultPathTemp.size()-1);
                    state[i]=0;
                    state[j]=0;
                    resultTemp-=maxTime;
                }
            }
        }
        if(returnTime!=0){
            resultPathTemp.remove(resultPathTemp.size()-1);
            resultTemp-=returnTime;
        }
    }

    /**
     * 某一次返回需要的时间.
     * 我们这里只选择最短过桥需要的时间，因为只是送灯，所以选择一个需要时间最短的人来送灯。
     * 这里进行了简化，必须要求time数组是从小到大的顺序排列
     * @return
     */
    private int returnTime() {
        for(int i=0;i<state.length;i++){
            if(state[i]==1){
                resultPathTemp.add((i+1)+"");
                state[i]=0;
                return time[i];
            }
        }
        return 0;
    }

    /**
     * 判断是否完成全部人过桥
     * @return
     */
    private boolean complete() {
        return Arrays.stream(state).filter(i->i==1).count()==state.length;
    }

    /**
     * 进行时间的初始化操作
     */
    private  void init() {
        time[0]=1;
        time[1]=3;
        time[2]=5;
        time[3]=6;
    }



}
